\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
%\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}

\usepackage{color}
\usepackage{url}
\definecolor{lnk}{rgb}{0,0,0.4}
\usepackage[colorlinks=true,linkcolor=lnk,citecolor=blue,urlcolor=blue]{hyperref}

\newcommand{\func}[2]{\texttt{#1}(#2)\\}
\newcommand{\tab}{\hspace*{2em}}
\newcommand{\FOR}{\textbf{for }}
\newcommand{\TO}{\textbf{ to }}
\newcommand{\IF}{\textbf{if }}
\newcommand{\WHILE}{\textbf{while }}
\newcommand{\THEN}{\textbf{ then }}
\newcommand{\ELSE}{\textbf{else }}
\newcommand{\RET}{\textbf{return }}
\newcommand{\MOD}{\textbf{ \% }}
\newcommand{\OR}{\textbf{ or }}
\newcommand{\AND}{\textbf{ and }}
\newcommand{\tOde}[1]{\tab {\small{$\mathcal{O}(#1)$}}}
\newcommand{\Ode}[1]{\small{$\mathcal{O}(#1)$}}
\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}
\newenvironment{pseudo}{\begin{tabular}{ll}}{\end{tabular}\VSP}

\newcommand{\gra}[1]{\noindent\includegraphics[scale=.60]{#1}\\}
\newcommand{\gram}[1]{\noindent\includegraphics[scale=.45]{#1}}
\newcommand{\dirmail}[1]{\normalsize{\texttt{#1}}}

\title{{\sc\normalsize Algoritmos y estructuras de datos III}\\{\bf Trabajo Práctico Nº2}}
\author{\begin{tabular}{lcr}Carla Livorno & 424/08 & \dirmail{carlalivorno@hotmail.com}\\Thomas Fischer & 489/08 & \dirmail{tfischer@dc.uba.ar}\\Kevin Allekotte & 490/08 & \dirmail{kevinalle@gmail.com} \end{tabular}}
\date{\VSP \normalsize{Octubre 2009}}
\begin{document}
\begin{titlepage}
\maketitle
\end{titlepage}
\tableofcontents
\newpage

	\begin{section}*{Introducción}	\addcontentsline{toc}{section}{Introducción}
						
	Este trabajo tiene como objetivo la aplicación de diferentes técnicas algoritmicas para la resolución de tres problemas modelados con grafos, el cálculo de complejidad teórica en el peor caso de cada algoritmo implementado, y posterior verificación empírica.
	
	El lenguaje utilizado para implementar los algoritmos de todos los problemas fue \texttt{C++}.

	\end{section}
	\begin{section}{Problema 1}
		\textit{Sea G un grafo en el cual cada eje tiene asociado un peso $p(e)$. Determinar el peso de un matching de peso máximo para el caso en que G es un ciclo simple de $n\geq 3$ vértices.}
		\begin{subsection}{Explicación}

			Dado que queremos un matching que maximice el peso, nos encontramos con un problema de optimización.\\
			
			%Para calcular la solución óptima, tenemos que calcular subproblemas que se superponen, lo que llevaria a resolver muchas veces un mismo subproblema, y observando tambien que cumple un principio de optimalidad, usamos programación dinámica para su resolución\\ 

			Dado un matching de peso máximo, se cumple la siguiente propiedad:\\
			
			\textit{Todo sub-matching debe ser tambien de peso máximo porque de no ser así, podría reemplazar ese sub-matching por otro de mayor peso y de esta forma obtener un matching mas pesado que el primero.}\\
			
			Podemos plantear el problema como un problema recursivo. Decidimos resolverlo con programación dinámica porque tenemos el principio de optimalidad recién mencionado y además tenemos que resolver subproblemas que se superponen (osea que necesitamos muchas veces el resultado de la función con los mismos parámetros).

			Para esto pensamos al ciclo como un grafo lineal, y luego solucionaremos la unión de las puntas.

			El matching de peso máximo que se puede formar hasta el eje $i$ es el máximo entre el matching que se puede formar hasta el eje $i-2$ y el que se puede formar hasta el $i-3$ más el peso de $i$.
			
			Entonces {\small $$ \texttt{match\_max}(i) := \begin{cases} \texttt{peso}(i)+max(\texttt{match\_max}(i-2), \texttt{match\_max}(i-3)) & i\geq 0 \\ 0 & i<0 \end{cases} $$}
			
			Esto vale porque en un matching no puede haber 2 ejes que compartan uno de sus extremos (si elegimos el eje $i$ no podríamos elegir también el $i-1$), y como queremos un matching máximo (y todos los pesos son positivos) no debemos dejar afuera más de 2 ejes consecutivos porque sino podríamos agregar el del medio y obtendríamos uno de peso mayor.\\
			
			Nuestro algoritmo recorre los ejes en orden y al peso de cada uno le suma el máximo entre el valor del eje $i-2$ y el valor del eje $i-3$. Con esto vamos resolviendo sucesivamente la función \texttt{match\_max} para cada eje hasta llegar al final.\\
			
			Cuando llegamos al último eje pueden pasar 2 cosas:
			\begin{itemize}
			\item El matching de peso máximo que encontramos para el grafo lineal es también un matching para el ciclo porque no usamos el primer y el ultimo eje a la vez. Entonces ningún par de ejes de los que elegimos comparten un extremo.
			
			\item El matching que encontramos para el grafo lineal usa el primer y el último eje, entonces no es un matching en el ciclo. En este caso tenemos que decidir con cuál de ambos nos quedamos, y restamos al resultado el valor del otro (Nos quedamos con el de peso máximo).
			
			\end{itemize}
			
			El resultado del problema original es el máximo entre los valores que quedaron en los últimos 3 ejes porque si eligieramos el valor que está en otro eje entonces podríamos agregar a ese matching alguno de los últimos ejes y entonces no sería un máximo.
			\begin{subsubsection}{Análisis de complejidad}
				\noindent \textbf{Complejidad temporal:}

				Dado que recorremos las aristas en orden, y a cada una le sumamos el máximo entre dos pesos calculados anteriormente, el costo del algoritmo resulta ser \Ode{m} donde m es la cantidad de aristas del grafo (tamaño de la entrada).\\

				\noindent \textbf{Complejidad espacial:}

				Dado que para ahorrarnos repetir calculos guardamos los resultados previamente calculados en un arreglo cuyo tamaño es la cantidad de aristas del ciclo (mismo arreglo donde recibimos los pesos de las aristas).

				Y por otro lado tenemos otro arreglo del mismo tamaño para saber donde inicia el matching.\\

				La complejidad espacial resulta ser \Ode{2m} = \Ode{m} con m cantidad de aristas del grafo.
			\end{subsubsection}

		\end{subsection}
		\begin{subsection}{Detalles de la implementación}
			Guardamos los pesos de las aristas en un arreglo en el orden en que aparecen en el ciclo (de la misma forma que estan en el archivo de entrada).

			Además guardamos otro arreglo del mismo tamaño en el cual marcamos para cada arista el número de la primer arista del matching al que pertenece, es decir 0 o 1 ya que en un principio al matching de cada arista excluyendo al de la última pertenece alguna de las dos (la primer arista o la segunda). Este arreglo nos sirve para calcular el peso del matching que incluye a la última arista.

			Si el matching al que pertenece la última arista tambien incluye a la primera, descartamos la de menor peso (porque no pueden pertencer ambas al mismo matching en el ciclo). Por esto mismo si en algún momento los pesos calculados anteriormente empatan nos quedamos preferentemente con el matching que no proviene de la primer arista, ya que a este le podemos sumar el peso de la última, y obtener un peso total mayor (si eligiesemos el que viene de la primer arista para incluir a la última deberiamos restar la primera).
		\end{subsection}
		\begin{subsection}{Pruebas y Resultados}
			Como podemos observar en los gráficos, los resultados muestran que el algoritmo claramente es lineal respecto al tamaño de entrada.
			Esto se corresponde con la complejidad teórica calculada.

			Además vemos que no hay variaciones en la ejecución del algoritmo, o sea, dado un tamaño de entrada, el tiempo de ejecución depende exclusivamente de este.
			
			\gra{ej1_counts.png}
			
			\gra{ej1_times.png}
		\end{subsection}
	\end{section}

	\begin{section}{Problema 2}
		\textit{Dada la altura de la marea, junto con la lista de vallas construidas, determinar la superficie del islote que no se inunda.}
		\begin{subsection}{Explicación}
			Armamos el mapa de las vallas que estan por arriba del nivel de la marea a partir de los datos de entrada. El mapa está representado por una matriz donde cada elemento de ésta es un metro cuadrado de la isla en la misma dispocisión. En cada celda está indicado en qué direciones la misma está protegida por vallas.
			
			Usando bfs y sabiendo que la celda $(0,0)$ siempre se inunda, inundamos todo el terreno posible. 
			
			La superficie total de isla menos la superficie inundada es el resultado del problema (superficie seca).
			El bfs comienza con una cola que contiene solo la celda $(0,0)$. Para cada elemento de la cola marca como inundadas las celdas adyacentes si no hay una valla en esa dirección (y que no esten inundadas) y las agrega a la cola. Repite este paso hasta que la cola este vacia, lo cual significa que ya inunde todo lo que podia inundar.			

			\begin{subsubsection}{Análisis de complejidad}
			El bfs recorre el mapa agregando cada celda a lo sumo una vez a la cola y recorre todos sus adyacentes. Como la cantidad de celdas adyacentes es constante (a lo sumo 4) entonces la complejidad del bfs es \Ode{n} donde en $n$ es el tamaño del mapa.
			
			Además cuando arma el mapa el algoritmo recorre para cada valla todas las celdas adyacentes a ella marcando la dirección en que la misma esta protegida.
			Como a lo sumo cada celda es adyacente a 4 vallas (porque las vallas comparten no más de un punto), cada celda es recorrida hasta 4 veces.
			Entonces la complejidad de esto tambien es \Ode{4n} = \Ode{n}.

			Por lo tanto la complejidad del algoritmo es \Ode{n+n} = \Ode{n}.
			
			En este problema no tiene sentido dar la complejidad en función del tamaño de entrada (cantidad de vallas) ya que la misma no es proporcional al tamaño del mapa.
			\end{subsubsection}

		\end{subsection}
		\begin{subsection}{Detalles de la implementación}
			Cuando leemos la entrada descartamos directamente las vallas que son más bajas que el nivel de la marea porque éstas no van a afectar la superficie que se inunda.\\
			
			El tamaño del mapa que creamos es la superficie en metros cuadrados del mínimo rectangulo en el cual puede inscribirse el islote, o sea desde la mínima coordenada $X$ e $Y$ de la valla que se encuentra más al suroeste hasta la máxima coordenada de la valla que se encuentra más al noreste respectivamente, más un borde de un metro cuadrado en cada dirección.
	
			Dado que el borde no tiene vallas el bfs lo va inundar y de esta forma se va a producir la inundanción de las casillas contiguas al mismo (si el borde no estuviese la inundación seria solo desde el extremo sureste de la isla, es decir desde la celda $(0,0)$, por lo que dependiendo de la disposición de las vallas habria celdas que no serian alcanzadas por el agua a pesar de no estar protegidas y esto no se condice con lo que realmente ocurriria ya que es una isla y esta rodeada de agua). 
			Es decir que agregar el borde nos permite simular que el agua ingresa en todas las direcciones.\\
			
			Cuando creamos el mapa tenemos que indicar en cada celda hacia cuales direcciones puede 'fluir' el agua, es decir, cuáles direcciones estan bloqueadas por vallas y cuáles no. Para lograr esto definimos las constantes \texttt{W=1, S=2, E=4, N=8}, y asignamos a cada celda la suma de las direcciones que están bloqueadas. Por ejemplo, una celda que esta bloqueada en las direcciones Norte y Sur tendrá un valor de \texttt{10}. Además definimos \texttt{I=16} que significa que la celda está inundada.
			
			Con estas constantes (potencias de 2) podemos preguntar si por ejemplo la dirección norte está bloqueada haciendo \texttt{Celda \& N > 0} (AND bit a bit). Esto nos permite guardar el mapa en un \texttt{array} de \texttt{int} y operar sólo con sumas, restas y \texttt{\&}.
		\end{subsection}
		\begin{subsection}{Pruebas y Resultados}
			
			Para analizar la correctitud del algoritmo \texttt{flood} hicimos una modificación del programa que devuelve el mapa inundado en vez del area de la superficie seca, y un python script que genera instancias aleatorias del problema y dibuja las vallas y pinta las partes inundadas segun la salida del programa.
			(Líneas negras: vallas altas, líneas grises: vallas por debajo del nivel de la marea, área celeste: superficie inundada, área blanca: superficie seca).
			
			Observando los resultados podemos analizar la correctitud del algoritmo.\\
			\gram{ej2_mapa1.png}
			\gram{ej2_mapa2.png}\\
			\gram{ej2_mapa3.png}
			\gram{ej2_mapa4.png}\\\\


			Como podemos ver en los gráficos siguientes, las muestras de tiempo y cantidad de operaciones tomadas de la ejecución están siempre por debajo de la curva $c\times n$. Esto parece corroborar la complejidad teórica calculada.

			La variación que vemos en los tiempos y operaciones del algoritmo, se deben a la variedad de cantidad de vallas y superficie seca que tienen los tableros. Los tableros son generados al azar, con una cantidad de vallas aleatoria en función del tamaño del mapa.
			
			Mientras más superficie seca encuentra el BFS, menos nodos va a encolar en la cola, lo que reduce la cantidad de veces que se ejecuta el ciclo.
			
			Por ejemplo, la cantidad de operaciones de una instancia con pocas vallas altas y mucha superficie seca es mucho menor que la de una instancia con muchas vallas y/o poca superficie seca.

			\gra{ej2_counts.png}
			
			\gra{ej2_times.png}
		\end{subsection}
	\end{section}
	
	\begin{section}{Problema 3}
		\textit{Los intregrantes del grupo Coppersmith deben conocerse entre sí mientras que los intregrantes del grupo Winograd no deben conocerse mutuamente. Encontrar las personas para formar cada grupo especial, en caso de que tales personas existan.}
		\begin{subsection}{Explicación}
			A partir de la entrada, generamos la matriz de adyacencia $A$ correspondiente. Dicha matriz tiene un 1 en la posición $(i,j)$ y en la posición $(j,i)$ si la persona $i$ se conoce con la persona $j$ y un cero si no se conocen.

			Para armar el grupo $Coppersmith$ necesitamos encontrar el grupo de tres personas lexicograficamente más chico en el que las tres se conocen entre sí, que equivale a encontrar el ciclo de longitud tres lexicograficamente más chico.

			Para esto calculamos el cuadrado de la matriz de adyacencia, $A^2$ (usando el algoritmo de \textit{Strassen}). Dicha matriz contiene en cada posición $(i,j)$ la cantidad de caminos de longitud dos entre $i$ y $j$. 

			Tambien, calculamos la diagonal de $A^3$. Esta contiene en $(i,i)$ la cantidad de caminos de longitud tres de $i$ hasta $i$. Si esta posición es mayor a cero significa que la persona $i$ pertenece a al menos un ciclo de longitud tres.
			
			Luego, recorremos esta diagonal en orden lexicografico. Cuando encontramos una posición $A^3_{i,i}$ distinta de cero es porque esa persona $i$ es parte de un grupo de tres personas que se conocen entre sí.
			
			Para encontrar a la segunda persona $j$ que forma parte del grupo \textit{Coppersmith} buscamos la siguiente posición de la diagonal que sea distinta de cero y que haya un camino de longitud dos y otro de longitud uno entre $i$ y $j$ (verificando que la posición $(i,j)$ sea distinta de cero en $A^2$ y en $A$ respectivamente).
			
			El ultimo intregrante $k$ es el indice de la siguiente posición $A^3_{k,k}$ en la diagonal que sea distinto de cero y que conoce a $i$ y a $j$ ($A_{k,i} \neq 0$ y $A_{k,j} \neq 0$).
			
			Si $i$,$j$ y $k$ existen y cumplen con esas condiciones, hay un ciclo de longitud tres que contiene a todos ellos (entonces $i$,$j$ y $k$ se conocen entre sí), y el grupo $(i,j,k)$ es el lexicográficamente menor de todos los posibles porque elegimos siempre el menor de todos los que cumplen con las condiciones mínimas para pertenecer al grupo, y $i\leq j\leq k$

			Para encontrar los integrantes del grupo \textit{Winograd} hicimos el mismo prcedimiento pero con el grafo complemento. La matriz de adyacencia $A'$ de este grafo es la matriz $A$ pero intercambiando los 0's por 1's y los 1's por 0's excepto en la diagonal.

			\begin{subsubsection}*{Algoritmo de Strassen} \addcontentsline{toc}{subsubsection}{Algoritmo de Strassen}

				El Algoritmo de Strassen es un algoritmo recursivo.
				Sean $\mathbf{A}$ y $\mathbf{B}$ las matrices que quiero multiplicar, tales que $\mathbf{A}, \mathbf{B} \in R^{2^k \times 2^k}$ (si los lados no cumplen con el tamaño, se pueden extender las matrices llenando los espacios nuevos con ceros).

				Puedo dividir $A$ y $B$ en cuatro partes de tamaños iguales ($2^{k-1} \times 2^{k-1}$) de la siguiente manera:

				$$\mathbf{A} =
				\begin{bmatrix}
				\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
				\mathbf{A}_{2,1} & \mathbf{A}_{2,2}
				\end{bmatrix}
				\mbox { , }
				\mathbf{B} =
				\begin{bmatrix}
				\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
				\mathbf{B}_{2,1} & \mathbf{B}_{2,2}
				\end{bmatrix}
				$$ \\

				\noindent Podemos calcular las siguientes 7 matrices haciendo sumas, restas y multiplicaciones de las submatrices de $\mathbf{A}$ y $\mathbf{B}$\\

				\noindent $ \mathbf{M}_{1}:= (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2}) $ \\
				$\mathbf{M}_{2}= (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}$ \\
				$\mathbf{M}_{3}= \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})$ \\
				$\mathbf{M}_{4}= \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})$ \\
				$\mathbf{M}_{5}= (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}$ \\
				$\mathbf{M}_{6}= (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})$ \\
				$\mathbf{M}_{7}= (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$ \\

				\noindent ,donde los productos entre matrices los resolvemos recursivamente con el mismo algoritmo.
				
				\newpage
				
				\noindent Luego podemos obtener las siguientes 4 matrices haciendo sumas y restas sobre las recién calculadas:\\

				\noindent $ \mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7} $ \\
				$\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}$\\
				$\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}$\\
				$\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}$\\

				\noindent Finalmente obtenemos $\mathbf{C} = \mathbf{A} \times \mathbf{B}$, $\mathbf{C} \in R^{2^k \times 2^k}$ como

				$$ \mathbf{C} =
				\begin{bmatrix}
				\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
				\mathbf{C}_{2,1} & \mathbf{C}_{2,2}
				\end{bmatrix} $$

				La ventaja de usar este algoritmo frente al método tradicional de multiplicación de matrices, es que este último tiene una complejidad teórica un poco menor ($c \times n^{2.85}$ vs $c' \times n^3$).

				No obstante, la constante $c$ de la complejidad del algoritmo de strassen es mucho mayor que la del algoritmo tradicional ,$c'$. Por esto decidimos resolver los productos entre matrices suficientemente chicas (de tamaño menor a un umbral (constante)) con el método tradicional.

				

			\end{subsubsection}

			\begin{subsubsection}{Análisis de complejidad}

				\begin{pseudo}
					\func{cw}{A}
					\tab $Coppersmith \gets grupo(A)$ & \Ode{n^{2.83}}	\\
					\tab $A' \gets complemento(A)$ & \Ode{n^2} \\
					\tab $Winograd \gets grupo(A')$ & \Ode{n^{2.83}} \\
					\tab \RET $Coppersmith + Winograd$ \\
					\\
					\func{grupo}{A}
					\tab $A2 \gets cuadrado(A)$ & \Ode{n^{2.83}} \\
					\tab $i \gets min\{i\ /.\ A^3_{i,i}>0\}$ & \Ode{n}\\
					\tab $j \gets min\{j\ /.\ A^3_{j,j}>0 \AND A^2_{j,i}>0 \AND A_{j,i}>0\}$ & \Ode{n}\\
					\tab $k \gets min\{k\ /.\ A^3_{k,k}>0 \AND A^3_{k,i}>0 \AND A^3_{k,j}>0\}$ & \Ode{n}\\
					\tab $\IF \exists i,j,k \THEN \RET (i,j,k)$\\
					\tab $\ELSE \RET (0,0,0)$\\
					\\
					\func{cuadrado}{A}
					\tab $A \gets lados2n(A)$ & \Ode{n^2} \\
					\tab $A2 \gets strassen(A,A)$ & \Ode{n^{2.83}} \\
					\tab $A2 \gets tamanioOriginalDeA(A2)$ & \Ode{n^2} \\
					\tab \RET $A2$ \\
					\\
					\texttt{complemento}(A) & \Ode{n^2}\\
					\tab $\FOR i\gets 0 \TO n$\\
					\tab\tab $\FOR j\gets 0 \TO n$\\
					\tab\tab\tab $\IF i\neq j \THEN A'_{i,j} \gets \neg A_{i,j}$\\
					\tab\tab\tab $\ELSE A'_{i,j} \gets A_{i,j}$\\
					\tab $\RET A'$\\
				\end{pseudo}
				
				Sea $n$ el tamaño de las matrices $\mathbf{A}$ y $\mathbf{B}$ ($\mathbf{A},\mathbf{B} \in R^{n\times n}$).
				La complejidad del algoritmo de strassen es la complejidad de calcular los $\mathbf{M}_{i}$, calcular los $\mathbf{C}_{i}$ y finalmente integrarlos para generar la matriz resultante $\mathbf{C}$. \\

				\begin{itemize}

					\item Cada $\mathbf{M}_{i}$ es calculado sumando y restando matrices de tamaño $n/2$, (\Ode{(n/2)^2}), y luego aplicando una multiplicacion que se calcula mediante una llamada recursiva al algoritmo de strassen. En total son 7 llamados recursivos con matrices de tamanio $n/2$.

					\item Calcular los $\mathbf{C}_{i}$ (de tamaño $n/2$) en función de sumas y restas de los $\mathbf{M}_i$, lo cuál tiene un costo de \Ode{(n/2)^2}.

					\item Por último, integrar los $\mathbf{C}_i$ en la matriz resultante, que cuesta \Ode{n^2}.

				\end{itemize}

				Si llamamos $T(n)$ a la complejidad del algoritmo para una entrada de tamaño $n$, podemos escribirla como:
				$$ T(n) = \begin{cases} 7\ T(n/2) + \mathcal{O}(n^2) & n>umbral \\ \mathcal{O}(n^3) & n\leq umbral \end{cases}$$
				
				El Teorema Maestro dice:\\
				$\mbox{dada una función de la forma } T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)  \;\;\;\; \mbox{donde} \;\; a \geq 1 \mbox{, } b > 1.$\\
				$\mbox{Si se cumple que } f(n) = \mathcal{O}\left( n^{\log_b \left( a \right) - \epsilon} \right) \mbox{, entonces vale que } T(n) = \Theta\left( n^{\log_b a} \right)$\\
				
				\noindent $a=7, b=2, f(n)=n^2 \in \mathcal{O}\left( n^{\log_b \left( a \right) - \epsilon} \right) \Rightarrow T(n) \in \mathcal{O}(n^{log_2(7)}) \approx \mathcal{O}(n^{2.81})$\\
%				Por inducción, $$\mbox{si } n\leq umbral\mbox{ , }T(n)=O(n^3)\subset O(umbral^3)\subset O(1)\subset O(n^{log_2(7)})$$
%				
%				Sup. $T(k)\in O(k^{log_2(7)}) \forall k<n$, qvq $T(n)\in O(n^{log_2(7)})$
%				$$T(n)=7\ T(n/2) + n^2=7((n/2)^{log_2(7)}+n^2) + O(n^2)$$
				
			\end{subsubsection}

		\end{subsection}

		\begin{subsection}{Detalles de la implementación}
			Para encontrar los integrantes de un grupo buscamos las posiciones de la diagonal de la matriz $A^3$ que sean distintas de cero, en orden. Dicha diagonal no está previamente calculada sino que tenemos una función que dadas $A^2$, $A$ y el indice $i$, nos indica si $A^3_{ii} > 0$ en \Ode{n}.\\

			Como la complejidad del algoritmo de \textit{Strassen} tiene una constante muy alta, decidimos calcular el producto entre matrices suficientemente chicas con el algoritmo tradicional.
			
			Para esto definimos un $umbral$: el tamaño máximo de las matrices 'suficientemente chicas'. Haciendo algunos experimentos prácticos y calculando la constante teóricamante buscamos el umbral a partir del cual el algoritmo de \textit{Strassen} es mejor que el tradicional.
			
			El resultado fue que para matrices de tamaño menor a $60000 \times 60000$ aproximadamente, debíamos recurrir al algoritmo trivial.

			Dado que generar matrices de esos tamaños nos es imposible, y ademas el tiempo de cálculo sería muy grande, los resultados obtenidos para casos de prueba usando este umbral hubiesen sido los resultados para el algoritmo trivial.
			Por esto decidimos usar un umbral mas pequeño para estudiar el comportamiento del algoritmo de Strassen en los resultados.\\

			Previo a llamar a la función de \textit{Strassen}, extendemos la matriz tal que su dimensión quede de la forma $2^n \times 2^n$ y rellenamos con ceros las posiciones agregadas.
			Esto nos permite dividir los lados de la matriz exactamente a la mitad en cada iteración del algoritmo.
			Luego de la multiplicación, eliminamos los campos generados anteriormente. \\
			
		\end{subsection}

		\begin{subsection}{Pruebas y Resultados}
			Como podemos observar en la siguientes figuras, el algoritmo parece alejarse cada vez mas de la curva $n^3$. Esto corrobora la complejidad teórica calculada.

			Los escalones que vemos en los gráficos, se deben a que el algoritmo de \textit{Strassen} requiere matrices de lado de la forma $n^2$ para su ejecución. 
			Entonces para cualquier tamaño de entrada distinto de una potencia de 2, el algoritmo tarda prácticamente lo mismo que para la potencia de 2 superior más próxima.

			\gra{ej3_counts.png}

			\gra{ej3_times.png}

			En el siguiente gráfico se aprecia claramente la gran diferencia que hay entre los tiempos de ejecución del algoritmo de \textit{Strassen} con $umbral=4$ y el algoritmo trivial de multiplicación de matrices.
			los tiempos de \textit{Strassen} son mucho mayores a pesar de que gana en complejidad teórica, ya que la constante que multiplica a la misma (en nuestra implementación) es del orden de $10^4$.

			En promedio, para valores de entrada de hasta 45 personas, el algoritmo del problema implementado con \textit{Strassen} tarda 5 veces mas que el mismo algoritmo usando la forma trivial.
			Dado que la multiplicación de matrices representa la única diferencia en los tiempos de ejecución del algoritmo, podemos concluír que el algoritmo de \textit{Strassen} tarda 5 veces mas en ejecutar una multiplicación entre dos matrices que el algoritmo trivial.

			\gra{ej3_times_vs.png}

		\end{subsection}
	\end{section}	
	
	\begin{section}{Compilación y ejecución de los programas}

		Para compilar los programas se puede usar el comando \texttt{make} en los directorios correspondientes a cada ejercicio. Esto requiere tener instalado el compilador \texttt{g++}. Los programas de cada ejercicio se pueden correr ejecutando \texttt{./matching}, \texttt{./flood} y \texttt{./cw} respectivamente.

		Los programas leen la entrada por \texttt{stdin} (entrada standard) y devuelven resultados por \texttt{stdout} (salida standard). Para leer la entrada de un archivo \texttt{Tp1EjX.in} y escribir la respuesta en un archivo \texttt{Tp1EjX.out} se puede usar la línea de comando \texttt{./(ejecutable) < Tp1EjX.in > Tp1EjX.out}.

		Para medir los tiempos de ejecución en vez de obtener el resultado del programa, se debe agregar seguido del nombre del ejecutable el parametro \texttt{time} (\texttt{./(ejecutable) time}) y opcionalmente se pueden pasar argumentos que indican la cantidad de tiempo mínima de ejecución y la cantidad de mediciones para cada instancia. Por ejemplo: \texttt{./(ejecutable) time 0.5 3} toma 3 mediciones de cada instancia (separadas por espacios); ejecuta el algoritmo $n$ veces hasta que tarde al menos 0.5 segundos y divide el resultado por $n$ (el segundo parametro define la presición de la medición).

		Para contar la cantidad de operaciones en vez de obtener el resultado del programa, se debe agregar seguido del nombre del ejecutable el parametro \texttt{count} (\texttt{./(ejecutable) count}). Esto devuelve la cantidad de operaciones que llevó ejecutar cada instancia.

		Para medir los tests de tiempo de ejecución y cantidad de operaciones se puede usar \texttt{make time} y \texttt{make count} respectivamente. Esto genera un archivo \texttt{time\_err.dat} o \texttt{count.dat} que contiene las mediciones de cada instancia de prueba. Se pueden graficar estas mediciones con \texttt{make plot\_time} y \texttt{make plot\_count}. Esto requiere de las librerías \texttt{python-tk} y \texttt{python-matplotlib} que pueden ser instaladas en sistemas debian ejecutando \texttt{sudo make config} en el directorio raíz del trabajo (\texttt{tp2/});

		Para el ejerecicio 2 (flood), existe una interface gráfica que se puede ver ejecutando \texttt{make view} en el directorio \texttt{tp2/Ej2\_flood/}. Esta interface también requiere la librería \texttt{python-tk} mencionada anteriormente.

	\end{section}
	
	\begin{section}{Conclusiones}

		En general, en todos los ejercicios logramos verificar que las complejidades calculadas teóricamente realmente correspondían con los resultados prácticos en la forma que esperabamos.
		Los ejercicios fueron implemenmtados de tal manera que cumpliesen con los requerimientos de eficiencia expuestos en el enunciado.

		En particular en el ejercicio 1 (matching), la técnica de programación dinámica nos permitio resolver un ejercicio en complejidad lineal, cuando a simple vista parecía por lo menos $n^3$.

		En el ejercicio 2 (flood), llamó la atención que el modelado del problema mediante grafos, y el aplicar un algoritmo muy simple sobre los mismos, llevara a una solución eficiente con un algoritmo relativamente sencillo.
		
		En el ejercicio 3 (\textit{Coppersmith - Winograd}) pudimos observar como un algoritmo, a pesar de tener una complejidad menor que otro, puede en la práctica ser muy malo con respecto al segundo.
		Esto nos muestra que el desempeño de un algoritmo en la practica con respecto a otro no necesariamente es equivalente a lo esperado a partir de la comparación de las complejidades obtenidas en el analisis teorico de los mismos. 
		Esto es debido a que la cota que nos da la complejidad es a partir de cierto tamaño de entrada, que a veces en la práctica, como en el caso del ejercicio 3, resulta ridículo.

	\end{section}
\end{document}

